public class Offer45 {
    public String minNumber(int[] nums) {
        // 本质上是一个排序问题, 字符串拼接
        // 如果 x + y > y + x, 那么字符串 x 比 y 大
        // 所以根据 x + y < y + x 进行排序
        int n = nums.length;
        String[] exp = new String[n];
        for (int i = 0; i < n; i ++)
            exp[i] = String.valueOf(nums[i]);

        quickSort(exp, 0, n - 1); // 排序

        String src = "";
        for (String elem : exp)
            src += elem;

        return src;
    }

    // 左闭右闭
    private void quickSort(String[] exp, int left, int right) {
        if (left >= right)  return; // 如果只有一个元素就没必要再分

        // 进行 基准 操作, 并返回 基准值下标
        int pivot = partition(exp, left, right);

        quickSort(exp, left, pivot - 1);
        quickSort(exp, pivot + 1, right);
    }

    private int partition(String[] exp, int left, int right) {
        // 以 左边第一个 作为基准值, 要从右边开始
        // 并且使用 挖坑法
        String pivot = exp[left];
        while (left < right) {
            // x + y < y + x
            // 右边先走, 找到比 基准值 小的, 所以要大了, 往左走
            while (left < right && (exp[right] + pivot).compareTo(pivot + exp[right]) >= 0) {
                right --;
            }
            exp[left] = exp[right];
            // 左边走, 找到比 基准值 大的, 所以如果小了, 就往右走
            while (left < right && (exp[left] + pivot).compareTo(pivot + exp[left]) <= 0) {
                left ++;
            }
            exp[right] = exp[left];
        }
        exp[left] = pivot;
        return left;
    }
}
